package dynamicProgramming.MatrixPathProblem;

/**
 * @author zxc
 * @date 2023/01/24 15:29
 **/
/**
 * @author zxc
 * @date 2023/01/24 15:20
 **/
/**
 * 题目 ：路径的数目
 * 题目详述 ：
 * 一个机器人位于一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 * 问总共有多少条不同的路径？
 *
 * 提示：
 * 1 <= m, n <= 100
 * 题目数据保证答案小于等于 2 * 109
 */
public class UniquePaths03 {
    /**
     * 思路 ：
     * 假设f(i,j)为机器人当前所在位置可能的路径数目;
     * 1.考虑特殊情况
     * （1）当i == 0时，同时又由于机器人只能够向右/下走，所以f(0,j) == 1（只可能是机器人向右走，直至走到坐标(0,j)为止）
     * （2）当j == 0时，同时又由于机器人只能够向右/下走，所以f(i,0) == 1（只可能时机器人向下走，直至走到坐标(i,0)为止）
     * 2.考虑一般情况
     * 当i > 0 && j > 0时，则f(i,j) = f(i-1,j) + f(i,j-1);
     * ===> 可以大致理解为，要求去f(i,j),只需要在f(i-1,j)向右走一步 || f(i,j-1)向下走一步;
     * @param m
     * @param n
     * @return
     */
    // 迭代代码实现
    public int uniquePaths(int m, int n) {
        // 迭代实现 ：即，f(i,j)为(i + 1) * (j + 1)大小网格的所以可能路线数量;
        int [][] temp = new int[2][n];
        // 初始化temp[0][0];
        temp[0][0] = 1;
        // （1）特殊情况 ：
        // 即，i == 0（即，前往坐标(i,0)的话，机器人只能够向右边走）
        // || j == 0（即，前往坐标(0,j)的话，机器人只能够向下边走）
        for(int j = 1;j < n;j++){
            temp[0][j] = 1;
        }
        // for循环 ：遍历所有可能到达的坐标坐标;
        // 普通情况 ：temp[i][j] = temp[i-1][j] + temp[i][j-1];
        for(int i = 1;i < m;i++){
            // 即，仅仅使用 2行j列的二维数组来保存结果 && 同时又由于每次都不给temp[i % 2][0]赋值;
            // ===》 所以我们选择每次给temp[i % 2][j]进行赋值的时候，即先给temp[i % 2][0]赋值;
            temp[i % 2][0] = 1;
            for(int j = 1;j < n;j++){
                temp[i % 2][j] = temp[(i - 1) % 2][j] + temp[i % 2][j - 1];
            }
        }
        return temp[(m - 1) % 2][n - 1];
    }
}
